package com.demo.java.OD501_550.OD504;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【组装最大可靠性设备(B卷-100分)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146472476
 */
public class OdMain {
    public static long result = -1;
    public static int s = -1;
    public static int n = -1;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 读取设备的预算、数量和设备信息
        s = in.nextInt();  // 预算
        n = in.nextInt();  // 设备数量
        int total = in.nextInt();  // 总设备数
        in.nextLine();  // 清空缓冲区

        // 存储设备信息：设备的类型、可靠性、价格
        List<long[]> items = new ArrayList<>();
        for (int i = 0; i < total; i++) {
            String input_str = in.nextLine();
            String[] tmp2 = input_str.split(" ");
            int[] nums = new int[tmp2.length];
            for (int j = 0; j < tmp2.length; j++) {
                nums[j] = Integer.parseInt(tmp2[j]);
            }
            // 添加设备信息：[类型, 可靠性, 价格]
            items.add(new long[]{nums[0] + 1, nums[1], nums[2]});
        }

        long left = 0;
        long right = total * 10000;  // 设置价格搜索的区间
        while (true) {
            if (left > right) {
                System.out.println(result);
                break;
            } else {
                long mid = left + (right - left) / 2;  // 计算二分查找的中值
                if (cal(mid, items)) {
                    result = mid;  // 如果满足条件，更新结果
                    left = mid + 1;  // 向右移动
                } else {
                    right = mid - 1;  // 向左移动
                }
            }
        }
    }

    // 计算是否能在给定的价格下选出合适的设备
    public static boolean cal(long x, List<long[]> devices) {
        long[] temp = new long[n + 1];  // 存储每个设备的可靠性
        for (int i = 1; i <= n; i++) {
            temp[i] = Integer.MAX_VALUE;  // 初始化为最大值
        }
        int j = 0;
        while (true) {
            if (j >= devices.size()) {
                long all = 0;
                // 计算所有设备的可靠性总和
                for (int i = 1; i <= n; i++) {
                    all += temp[i];
                }
                // 如果所有设备的可靠性总和不超过预算，返回true
                return all <= s;
            } else {
                // 如果设备的可靠性满足要求，更新设备的可靠性
                if (devices.get(j)[1] >= x) {
                    temp[(int) devices.get(j)[0]] = Math.min(temp[(int) devices.get(j)[0]], devices.get(j)[2]);
                }
            }
            j += 1;
        }
    }
}